package 力扣.二分;

import java.util.HashMap;
import java.util.Map;

public class 最小覆盖子串76 {
    String ans;
    int len;
    public String minWindow(String s, String t) {
        if(s == null || s.length() == 0 || t == null || t.length() == 0){
            return "";
        }
        int N = s.length();
        ans = null;
        len = Integer.MAX_VALUE;
        int l = t.length(),r = N + 1;
        while (l < r){
            int m = l + ((r - l) >> 1);
            int flag = getC(s,t,m);
            if (flag < 0){
                l = m + 1;
            }else {
                r = m;
            }
        }
        return l <= N ? ans : "";
    }

    /**
     * 从s中截取长度为m的子串，判断子串中是否包含t
     */
    private int getC(String s, String t, int m) {
        //如何判断一个字符串中是否包含另一个字符串
        HashMap<Character, Integer> mapt = new HashMap<>();
        HashMap<Character, Integer> maps = new HashMap<>();
        for (int j = 0; j < t.length(); j++) {
            char c = t.charAt(j);
            mapt.put(c, mapt.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        for (int i = 0; i < s.length(); i++) {


            char c = s.charAt(i);
            maps.put(c,maps.getOrDefault(c, 0) + 1);
            if (i < m -1){
                continue;
            }

            boolean flag = true;
            for (Map.Entry<Character,Integer> entry: mapt.entrySet()) {
                if (maps.containsKey(entry.getKey())){
                    if (!((maps.get(entry.getKey()) >= entry.getValue()))){
                        flag = false;
                    }
                }else {
                    flag = false;
                }
            }
            if (flag){
                if (m < len){
                    len = m;
                    ans =  s.substring(left,i+1);
                }
                return 0;
            }

            char de = s.charAt(left);
            int cnt = maps.get(de);
            if (cnt > 1){
                maps.put(de, cnt-1);
            }else {
                maps.remove(de);
            }
            left++;

        }
        return -1;
    }






    private String ans2 = new String("");
    private final int SZ = 256;
    private int[] bcnt = new int[SZ];
    private int[] acnt = new int[SZ];
    private int alen = 0;
    private int blen = 0;
    private int buniq = 0;

    private int getC2(String A, String B, int len) {
        // 注意这个映射函数的作用
        // 也同时完成了找到最优值的功能
        // 每次找到最优结果之后，就将它放到ans里面
        for (int i = 0; i < SZ; i++) {
            acnt[i] = 0;
        }
        int large_cnt = 0;
        for (int i = 0; i < alen; i++) {
            char c = A.charAt(i);
            if (++acnt[c] == bcnt[c]) {
                large_cnt++;
            }

            if (i < len - 1) {
                continue;
            }

            if (large_cnt >= buniq) {
                ans2 = A.substring(i + 1 - len, i + 1);
                return 0;
            }

            // 移除长度为len的开头的那个字符
            // 为后面的计数做准备。
            char old = A.charAt(i + 1 - len);
            if (bcnt[old] > 0 && acnt[old]-- == bcnt[old]) {
                large_cnt--;
            }
        }

        return -1;
    }
}
